package org.apache.commons.graph.algorithms.flow

import org.apache.commons.graph.CommonsGraph.findMaxFlow
import org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseLabeledWeightedEdge
import org.apache.commons.graph.model.BaseWeightedEdge
import org.apache.commons.graph.model.DirectedMutableGraph
import org.apache.commons.graph.weight.primitive.IntegerWeightBaseOperations
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Test for Edmonds-Karp algorithm implementation.
 * The test graph is available on
 * [Wikipedia](http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm#Example).
 */
class EdmondsKarpTestCase {
    @Test
    fun testFindMaxFlowAndVerify() {
        val a = BaseLabeledVertex("A")
        val g = BaseLabeledVertex("G")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    val d = addVertex(BaseLabeledVertex("D"))
                    val e = addVertex(BaseLabeledVertex("E"))
                    val f = addVertex(BaseLabeledVertex("F"))
                    addVertex(g)

                    addEdge(BaseLabeledWeightedEdge<Int>("A -> B", 3)).from(a).to(b)
                    addEdge(BaseLabeledWeightedEdge<Int>("A -> D", 3)).from(a).to(d)
                    addEdge(BaseLabeledWeightedEdge<Int>("B -> C", 4)).from(b).to(c)
                    addEdge(BaseLabeledWeightedEdge<Int>("C -> A", 3)).from(c).to(a)
                    addEdge(BaseLabeledWeightedEdge<Int>("C -> D", 1)).from(c).to(d)
                    addEdge(BaseLabeledWeightedEdge<Int>("C -> E", 2)).from(c).to(e)
                    addEdge(BaseLabeledWeightedEdge<Int>("D -> E", 2)).from(d).to(e)
                    addEdge(BaseLabeledWeightedEdge<Int>("D -> F", 6)).from(d).to(f)
                    addEdge(BaseLabeledWeightedEdge<Int>("E -> B", 1)).from(e).to(b)
                    addEdge(BaseLabeledWeightedEdge<Int>("E -> G", 1)).from(e).to(g)
                    addEdge(BaseLabeledWeightedEdge<Int>("F -> G", 9)).from(f).to(g)
                }
            })

        // expected max flow
        val expected = 5

        // actual max flow
        val actual = findMaxFlow(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
            .from(a)
            .to(g)
            .applyingEdmondsKarp(IntegerWeightBaseOperations)

        Assert.assertEquals(expected, actual)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        val a = BaseLabeledVertex("A")
//        val g = BaseLabeledVertex("G")
//
//        // actual max flow
//        findMaxFlow(null as DirectedMutableGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Int?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
//            .from(a)
//            .to(g)
//            .applyingEdmondsKarp(IntegerWeightBaseOperations())
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullVertices() {
//        val a: BaseLabeledVertex? = null
//        val g: BaseLabeledVertex? = null
//
//        val graph =
//            DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>()
//
//        // actual max flow
//        findMaxFlow(graph)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
//            .from(a)
//            .to(g)
//            .applyingEdmondsKarp(IntegerWeightBaseOperations())
//    }

    @Test
    fun testSparse() {
        val a = BaseLabeledVertex("A")
        val g = BaseLabeledVertex("G")

        val graph: DirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>> =
            newDirectedMutableGraph(object :
                AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Int>>() {
                override fun connect() {
                    addVertex(a)
                    val b = addVertex(BaseLabeledVertex("B"))
                    val c = addVertex(BaseLabeledVertex("C"))
                    addVertex(BaseLabeledVertex("D"))
                    addVertex(BaseLabeledVertex("E"))
                    addVertex(BaseLabeledVertex("F"))
                    addVertex(g)

                    addEdge(BaseLabeledWeightedEdge<Int>("A -> B", 3)).from(a).to(b)
                    addEdge(BaseLabeledWeightedEdge<Int>("B -> C", 4)).from(b).to(c)
                }
            })

        // expected max flow
        val expected = 0

        // actual max flow
        val actual = findMaxFlow(graph)
            .whereEdgesHaveWeights(BaseWeightedEdge<Int>())
            .from(a)
            .to(g)
            .applyingEdmondsKarp(IntegerWeightBaseOperations)
        Assert.assertEquals(actual, expected)
    }
}
